/*
 * @lc app=leetcode.cn id=34 lang=cpp
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 * 
 * 为了是复杂度降低，可以利用非降序排列的特性使用二分法查找，而非从前向后遍历
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
//原理：二分法查找目标元素和目标元素+1的最左序号
    int binary(vector<int>& nums, int target) {
        int left = 0,right = nums.size();
        while(left < right) {
            int mid = (left + right) / 2;
            //nums[mid] == target时也使右边界左移，直到左边界等于右边界为止，这时返回的元素就是最左元素
            //如果target+1或target查找不到,也应该是左边等于右边等于n
            if(nums[mid] >= target) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return left;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int left = binary(nums, target);
        int right = binary(nums, target + 1);
        if(left == n || nums[left] != target) {
            return {-1,-1};
        }
        return {left,right - 1};
    }
};

// @lc code=end

//第一次写法，就从前往后遍历的 Your runtime beats 95.19 % of cpp submissions
// vector<int> searchRange(vector<int>& nums, int target) {
//         int n = nums.size();
//         int a = -1,b = -1;
//         if(n == 0) {
//             return {a,b};
//         }
//         for(int i = 0;i < n;i++) {
//             if(nums[i] == target) {
//                 a = i;
//                 if(i == n - 1) {
//                     b = a;
//                     break;
//                 }
//                 for(int j = i + 1;j < n;j++) {
//                     if(nums[j] != nums[j-1]) {
//                         b = j - 1;
//                         break;  
//                     }else {
//                         b = j;
//                     }
//                 }
//                 break;
//             }
//         }
//         return {a,b};
//     }

